iT邦幫忙

2023 iThome 鐵人賽

DAY 5
0

前言

這次會先來介紹XOR跟一些它的特性,之後再來解題!

XOR

  • 經典文氏圖!
    https://ithelp.ithome.com.tw/upload/images/20230915/20162613oCgaeRoVor.png

只是覺得南瓜很可愛就想放一下XD

  • 為位元運算(把數字換二進位再去做xor)
  • 位元運算子 : “ ^ “,數學符號 : ⊕,e.g. a^b 、 a⊕b
  • 在條件A 及 B 2項都成立或2項都不成立時 = > 回傳False
  • 在條件A 及 B 中有一項成立及另一項不成立 = > 回傳True
  • 得出真值表
    https://ithelp.ithome.com.tw/upload/images/20230915/20162613pADvdQuAlD.png

特性

由以上可知

  • 當A = B,A⊕B都會為0,所以得出
    • A⊕B = 0、A⊕A = 0 => 相同數字去做XOR會互相抵消為0
  • 如B = 0且A != 0, 那麼A⊕B = A,所以得出
    • A⊕0 = A => 任何數字⊕0結果都會為那個數字
  • 如A = 1、B = 0,A⊕B跟B⊕A的結果相同(都為1),所以得出
    • A⊕B = B⊕A => XOR符合交換律

有交換律,感覺少了一點什麼,沒錯!XOR也符合結合律喔!不過要稍微想一下,我們回到真值表(懶得往上滑,所以我再放一次圖( •̀ ω •́ )✧)
https://ithelp.ithome.com.tw/upload/images/20230915/20162613WKvsblQg77.png

根據result可知,如果A + B為偶數(0、2)那麼結果為0,
反之,如果為奇數(1)那麼結果就為1
所以我們可以設一個函式Odd(),如A+B為奇數,那麼Odd(A+B)就會回傳奇數(1),
反之為偶數的話回傳偶數(0),代表我們可以把A⊕B寫成

  • A⊕B = Odd(A+B)

有了這個,我們來開始證明結合律!

  • 目標 : 證明 A⊕(B⊕C) = (A⊕B)⊕C

A⊕(B⊕C)
=A⊕(Odd(B+C))
=Odd(A+(Odd(B+C))

Odd(A+(Odd(B+C))意思是先把B跟C相加之後判斷奇偶,
如相加為奇回傳奇(1),
相加偶回傳偶(0),
之後再加A去判斷奇偶。
所以裡面Odd(B+C)也可以寫成B+C(因為B+C跟Odd(B+C)結果的奇偶性會是一樣的,
比如說B+C是偶數,代表Odd(B+C)會回傳偶,所以兩者結果都是偶數),
由此可得Odd(A+B+C)

=Odd(A+B+C)
=Odd(Odd(A+B)+C)
=(A⊕B)⊕C

  • 由以上可得知,A⊕(B⊕C) = (A⊕B)⊕C
  • XOR符合結合律

https://math.stackexchange.com/questions/293793/prove-xor-is-commutative-and-associative 想要更詳細、或著其他方式證明結合律的話可以看這個網址,主要是我被這個證明方式說服了,加上自己對於這種AND OR運算還不是很熟悉,所以就只介紹這個證明方式

特性小整理

符合以下

  • A⊕0 = A(恆等律)
  • A⊕A = 0(自我抵銷、歸零律)
  • A⊕B = B⊕A(交換律)
  • A⊕(B⊕C) = (A⊕B)⊕C(結合律)
  • A⊕B⊕B = A⊕0 = A(自反)

實作XOR

懂了XOR的特性以及觀念,我們先自己手算xor一次,之後再用code來驗證、實作一次吧!

先來隨便設兩個變數,A = 97、B = 15

  • 目標 : 輸出A XOR B的結果

  • 流程 : 先把A跟B轉為2進位,之後一個一個bit做xor,最後把結果轉回10進位得出答案

  • 先來把兩數轉二進位
    使用短除法,得到餘數之後由下到上就是該數的二進位!
    https://ithelp.ithome.com.tw/upload/images/20230915/20162613ZryoqOIkVm.png

  • 得 A = 1100001、B=1111,接下來做XOR

之後要一個一個做XOR的時候會發現一個大問題,那就是兩個長度不同!
解決方法為在比較短的左側去補零,我們上圖!紅色的0就是補0的部分
https://ithelp.ithome.com.tw/upload/images/20230915/20162613PmZNUIiNYp.png

而為甚麼在左側補0不會影響結果,我們放到最後再來!可以想想看XD

接下來要把結果換成10進位。如XOR result為1,就把它對應的2的次方取出來,結果為 110
https://ithelp.ithome.com.tw/upload/images/20230916/20162613j6g5LbGEi1.png
手算完後,我們用程式碼來進行驗證,有兩種方式,第一個為使用^來做XOR,第二種為使用pwntools函式庫中的xor()

所以使用時要記得from pwn import *

  • Code
from pwn import *
num1 = 97
num2 = 15

print("use ^ :", num1^num2)
print("use xor :", ord(xor(num1,num2)))

  • Output
    https://ithelp.ithome.com.tw/upload/images/20230915/201626138gieYLf00z.png

可知兩種方式結果都是一樣的(不過使用xor()他出來會直接轉成字符,所以我偷偷用了ord()把它變回數字),與我們手算的結果也相同!皆大歡喜R (°▽°)╯

小結

終於結束惹,OMG,位元運算的部分,對於我來說,理解有一點小小吃力,尤其是證明的時候(┬┬﹏┬┬)不過最後弄懂,也學到了好多咚咚
不過還沒完!還記得在實作XOR問的問題嗎,我們再來理解一下吧XD

為甚麼在左側補0不會影響結果

可以參考這張圖
https://ithelp.ithome.com.tw/upload/images/20230915/2016261358OrSAcZjH.png

由此可知,當二進位值為0的話,不管位於哪,乘出來的結果都會是0,所以可推得
int(101010,2) = int(00101010,2)
一樣用圖表顯示

https://ithelp.ithome.com.tw/upload/images/20230915/20162613DJFZLprJyd.png

下面為在左側加兩個0,但會發現,因為是乘0的關係,所以最後加起來的值是一樣的。

  • 推得,左側加0並不會影響最後結果!

理解完畢!今天大概就到這裡惹,休息!明天開始正式解題~

參考資料

XOR維基百科: https://zh.wikipedia.org/zh-tw/%E9%80%BB%E8%BE%91%E5%BC%82%E6%88%96

XOR文式圖 : https://www.cool3c.com/article/157771

XOR位元運算子介紹 : https://medium.com/@hyWang/xor-%E4%BD%8D%E5%85%83%E9%81%8B%E7%AE%97%E5%AD%90-1c25b4ae15fb

證明XOR結合律(Prove XOR is commutative and associative) : https://math.stackexchange.com/questions/293793/prove-xor-is-commutative-and-associative

兩數二進位長度不同做XOR : https://stackoverflow.com/questions/31520787/how-to-xor-two-binary-numbers-having-different-length

二進位算法 : https://tomchun.tw/tomchun/2015/11/11/1-91/

二進位轉十進位 : https://www.geeksforgeeks.org/binary-to-decimal/


上一篇
【Day 4】Encode統整筆記
下一篇
【Day 6】Introduction to CryptoHack 03 - XOR
系列文
資安小白的密碼學從0到1-CryptoHack平台解題紀錄31
圖片
  直播研討會
圖片
{{ item.channelVendor }} {{ item.webinarstarted }} |
{{ formatDate(item.duration) }}
直播中

尚未有邦友留言

立即登入留言